import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //设置虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        
        ListNode pre = dummyNode;
        //走left-1步到left前一个节点
        for(int i = 0; i < m - 1; i++ ) {
            pre = pre.next;
        }
        //2.走right-left+1步到right节点
        ListNode rightNode = pre;
        for(int i = 0; i < n-m+1; i++) {
            rightNode = rightNode.next;
        }
        //3.截取子段
        ListNode leftNode = pre.next;
        ListNode cur  = rightNode.next;
        //4.切断链表
        pre.next = null;
        rightNode.next = null;
        //5.反转局部链表
        ListNode newList = reverseLinkedList(leftNode);
        //6.接回原来的链表
        pre.next = rightNode;
        leftNode.next = cur;
        return dummyNode.next;
    }

    private ListNode reverseLinkedList(ListNode head) {
       ListNode newHead = null;
       while(head != null) {
        ListNode temp = head.next;
        head.next = newHead;
        newHead = head;
        head = temp;
       }
       return newHead;
    }
}